home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / prio.h < prev    next >
C/C++ Source or Header  |  1994-08-05  |  5KB  |  150 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  prio.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_PRIORITY_QUEUE_H
  17. #define LEDA_PRIORITY_QUEUE_H
  18.  
  19. #include <LEDA/impl/f_heap.h>
  20.  
  21. typedef f_heap_item pq_item;
  22.  
  23.  
  24. template<class ktype, class itype> 
  25.  
  26. class _CLASSTYPE priority_queue: public f_heap
  27. {
  28.  
  29. int  int_type()              const { return INT_TYPE(itype); }
  30. int  cmp(GenPtr x, GenPtr y) const
  31.                      { return compare(ACCESS(itype,x),ACCESS(itype,y)); }
  32. void clear_key(GenPtr& x)   const { Clear(ACCESS(itype,x)); }
  33. void clear_inf(GenPtr& x)   const { Clear(ACCESS(ktype,x)); }
  34. void copy_key(GenPtr& x)    const { x=Copy(ACCESS(itype,x)); }
  35. void copy_inf(GenPtr& x)    const { x=Copy(ACCESS(ktype,x)); }
  36. void print_key(GenPtr x)    const { Print(ACCESS(itype,x),cout); }
  37. void print_inf(GenPtr x)    const { Print(ACCESS(ktype,x),cout); }
  38.  
  39. public:
  40.  
  41. virtual pq_item insert(ktype k,itype i) 
  42.                               { return f_heap::insert(Convert(i),Convert(k)); }
  43.  
  44. virtual pq_item find_min()       const { return f_heap::find_min();}
  45.  
  46. virtual ktype   del_min()              { ktype x = key(find_min()); 
  47.                                          f_heap::del_min(); 
  48.                                          return x; }
  49.  
  50. virtual ktype key(pq_item x)     const { return ACCESS(ktype,f_heap::inf(x)); }
  51. virtual itype inf(pq_item x)     const { return ACCESS(itype,f_heap::key(x)); }
  52.  
  53. virtual void change_key(pq_item x,ktype k) 
  54.                                        { f_heap::change_inf(x,Convert(k)); }
  55. virtual void decrease_inf(pq_item x,itype i)
  56.                                        { f_heap::decrease_key(x,Convert(i)); }
  57.  
  58. virtual void del_item(pq_item x)       { f_heap::del_item(x); }
  59.  
  60. virtual int  size()    const { return f_heap::size(); }
  61. virtual bool empty()   const { return (size()==0) ? true : false; }
  62.  
  63. virtual pq_item first_item()          const { return f_heap::first_item(); }
  64. virtual pq_item next_item(pq_item it) const { return f_heap::next_item(it); }
  65.  
  66. priority_queue<ktype,itype>& operator=(const priority_queue<ktype,itype>& Q) 
  67. { return (priority_queue<ktype,itype>&)f_heap::operator=(Q); }
  68.  
  69.  priority_queue()  {}
  70.  priority_queue(const priority_queue<ktype,itype>& Q):f_heap(Q) {}
  71. ~priority_queue()  { f_heap::clear(); }
  72. };
  73.  
  74.  
  75. //------------------------------------------------------------------------------
  76. //
  77. // Priority queues with implementation parameter:
  78. //
  79. //   _priority_queue<keytype,inftype,prio_impl> 
  80. //
  81. //------------------------------------------------------------------------------
  82.  
  83. #define _priority_queue_class(ktype,itype,impl)\
  84. \
  85. class _CLASSTYPE _prio_class_(ktype,itype,impl) : private impl, public priority_queue<ktype,itype>\
  86. {\
  87. int int_type() const { return INT_TYPE(itype); }\
  88. \
  89. int cmp(GenPtr x, GenPtr y) const\
  90.                          { return compare(ACCESS(itype,x),ACCESS(itype,y)); }\
  91. void clear_key(GenPtr& x) const { Clear(ACCESS(itype,x)); }\
  92. void clear_inf(GenPtr& x) const { Clear(ACCESS(ktype,x)); }\
  93. void copy_key(GenPtr& x) const { x=Copy(ACCESS(itype,x)); }\
  94. void copy_inf(GenPtr& x) const { x=Copy(ACCESS(ktype,x)); }\
  95. void print_key(GenPtr x) const { Print(ACCESS(itype,x),cout); }\
  96. void print_inf(GenPtr x) const { Print(ACCESS(ktype,x),cout); }\
  97. \
  98. public:\
  99. \
  100. pq_item insert(ktype k,itype i) { return pq_item(impl::insert(Convert(i),Convert(k)));}\
  101. \
  102. pq_item find_min() const { return pq_item(impl::find_min());}\
  103. \
  104. ktype del_min() { pq_item it = find_min();\
  105.                   ktype    x = key(it);\
  106.                   del_item(it);\
  107.                   return x; }\
  108. \
  109. ktype key(pq_item x) const { return ACCESS(ktype,impl::inf(impl::item(x)));}\
  110. itype inf(pq_item x) const { return ACCESS(itype,impl::key(impl::item(x)));}\
  111. \
  112. void change_key(pq_item x, ktype k)\
  113. { impl::change_inf(impl::item(x),Convert(k)); }\
  114. \
  115. void decrease_inf(pq_item x,itype i)\
  116. { impl::decrease_key(impl::item(x),Convert(i));}\
  117. \
  118. void del_item(pq_item x) { impl::del_item(impl::item(x)); }\
  119. \
  120. int size() const { return impl::size(); }\
  121. bool empty() const { return (size()==0) ? true : false; }\
  122. \
  123. pq_item first_item() const { return pq_item(impl::first_item()); }\
  124. pq_item next_item(pq_item it) const { return pq_item(impl::next_item(impl::item(it))); }\
  125. \
  126. _prio_(ktype,itype,impl)& operator=(const _prio_(ktype,itype,impl)& Q) { return (_prio_(ktype,itype,impl)&)impl::operator=(Q); }\
  127. \
  128. _prio_class_(ktype,itype,impl)() {}\
  129. _prio_class_(ktype,itype,impl)(int n) : impl(n) {}\
  130. _prio_class_(ktype,itype,impl)(const _prio_(ktype,itype,impl)& Q)\
  131. : impl(Q) {}\
  132. \
  133. ~_prio_class_(ktype,itype,impl)() { impl::clear(); }
  134.  
  135.  
  136. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  137. #define _prio_class_(a,b,c) _priority_queue
  138. #define _prio_(a,b,c) _priority_queue<a,b,c>
  139. template <class ktype, class itype, class impl> 
  140. _priority_queue_class(ktype,itype,impl)
  141. };
  142. #else
  143. #define _priority_queue(a,b,c)         name4(a,b,c,_priority_queue)
  144. #define _prio_class_(a,b,c)            name4(a,b,c,_priority_queue)
  145. #define _prio_(a,b,c)                  name4(a,b,c,_priority_queue)
  146. #define _priority_queuedeclare3(_a,_b,_c) _priority_queue_class(_a,_b,_c) };
  147. #endif
  148.  
  149. #endif
  150.